package train48days;

import java.util.Scanner;

public class 星际战争 {
        public static void main(String[] args){
            int[] arr = new int[10001];
            arr[1] = 1;
            arr[2] = 2;
            for (int i = 3; i < 10001; i++) {
                arr[i] = arr[i-1]+arr[i-2];
                arr[i] = arr[i]%10000;
            }
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()){
                StringBuilder  sb=new StringBuilder();
                int n =sc.nextInt();
                for (int i = 0; i < n; i++) {
                    int xi= sc.nextInt();
                    sb.append(String.format("%04d",arr[xi]));
                }
                System.out.println(sb);
            }




//            int[] arr = new int[10001];
//            arr[1] = 1;
//            arr[2] = 2;
//            for(int i = 3;i < 10001;i++){
//                arr[i] = arr[i - 1] + arr[i - 2];
//                arr[i] =  arr[i] % 10000;
//            }
//           Scanner sc = new Scanner(System.in);
//            while(sc.hasNext()){
//                StringBuffer sb = new StringBuffer();
//                int n = sc.nextInt();
//                for(int i = 0;i < n;i++){
//                    int xi = sc.nextInt();
//                    sb.append(String.format("%04d",arr[xi]));
//                }
//                System.out.println(sb);
//            }
        }
    }
